<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 最长的顺子（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4>题目描述</h4> 
<p>斗地主起源于湖北十堰房县&#xff0c;据说是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的&#xff0c;如今已风靡整个中国&#xff0c;并流行于互联网上。</p> 
<p>牌型&#xff1a;单顺&#xff0c;又称顺子&#xff0c;最少5张牌&#xff0c;最多12张牌(3…A)不能有2&#xff0c;也不能有大小王&#xff0c;不计花色。</p> 
<p>例如&#xff1a; 3-4-5-6-7-8&#xff0c;7-8-9-10-J-Q&#xff0c;3-4-5-6-7-8-9-10-J-Q-K-A</p> 
<p>可用的牌 3&lt;4&lt;5&lt;6&lt;7&lt;8&lt;9&lt;10&lt;J&lt;Q&lt;K&lt;A&lt;2&lt;B(小王)&lt;C(大王)&#xff0c;每种牌除大小王外有四种花色</p> 
<p>(共有13×4&#43;2张牌)</p> 
<p>输入&#xff1a;</p> 
<ol><li>手上有的牌</li><li>已经出过的牌(包括对手出的和自己出的牌)</li></ol> 
<p>输出&#xff1a;</p> 
<ul><li>对手可能构成的最长的顺子(如果有相同长度的顺子&#xff0c;输出牌面最大的那一个)&#xff0c;</li><li>如果无法构成顺子&#xff0c;则输出 NO-CHAIN。</li></ul> 
<p></p> 
<h4>输入描述</h4> 
<p>输入的第一行为当前手中的牌</p> 
<p>输入的第二行为已经出过的牌</p> 
<p></p> 
<h4>输出描述</h4> 
<p>最长的顺子</p> 
<p></p> 
<h4>用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3-3-3-3-4-4-5-5-6-7-8-9-10-J-Q-K-A<br /> 4-5-6-7-8-8-8</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">9-10-J-Q-K-A</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3-3-3-3-8-8-8-8<br /> K-K-K-K</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">NO-CHAIN</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">剩余的牌无法构成顺子</td></tr></tbody></table> 
<h4>题目解析</h4> 
<p>本题我的解题思路分为两步&#xff1a;</p> 
<ol><li>求出对手的牌</li><li>基于对手的牌&#xff0c;求最长顺子</li></ol> 
<p>首先&#xff0c;对手的牌 &#61; 总牌 - 我的牌 - 已打出的牌</p> 
<p>这里主要难点在于&#xff0c;如何记录牌面对应的牌数量。我的思路是&#xff1a;</p> 
<p>定义一个数组count&#xff0c;将数组count的索引和牌面关联&#xff08;定义一个字典mapToV&#xff09;&#xff0c;数组count的元素值就是对应牌面的数量。</p> 
<p>这样可以得出一个数组&#xff1a;</p> 
<blockquote> 
 <pre>// count每个索引值对应一个牌面值&#xff0c;count元素值就是对应牌面的数量
// 牌面值               3  4  5  6  7  8  9  10 J  Q  K  A     2  B  C
// 索引值               3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
int[] count &#61; {0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 1};</pre> 
</blockquote> 
<p>然后&#xff0c;就可以很简单的完成&#xff1a;对手的牌 &#61; 总牌 - 我的牌 - 已打出的牌</p> 
<p></p> 
<p>比如用例1&#xff0c;对手的牌就可以表示为&#xff1a;</p> 
<blockquote> 
 <p>int[] count &#61; {0, 0, 0, 1, 1, 2, 2, 0, 3, 3, 3, 3, 3, 3, 3, 0, 4, 1, 1};</p> 
</blockquote> 
<p>接下来我们可以定义一个 L 指针&#xff0c;作为顺子的左边界&#xff0c;L指针的运动范围是count数组的索引3~索引10。</p> 
<blockquote> 
 <p>因为&#xff0c;顺子只能由牌面3~牌面A组成&#xff0c;因此左边界起始位置是牌面3&#xff0c;即索引3。而顺子至少要由5张牌组成&#xff0c;因此&#xff0c;左边界的结束位置是牌面10&#xff0c;即索引10&#xff0c;对应的顺子是10,J,Q,K,A。</p> 
</blockquote> 
<p>之后&#xff0c;定义一个临时右边界指针R&#xff0c;区间[L,R]之间就是顺子的范围&#xff0c;R的从L位置开始扫描&#xff1a;</p> 
<ul><li>如果count[R] &gt;&#61; 1&#xff0c;则可以加入顺子范围&#xff0c;之后R&#43;&#43;</li><li>如果count[R] &#61;&#61; 0&#xff0c;则顺子中断&#xff0c;此时&#xff0c;我们要看[L, R-1]的长度是否大于等于5&#xff0c;如果是&#xff0c;则是顺子&#xff0c;否则就不是顺子。</li></ul> 
<p>当顺子发生中断&#xff0c;则下一次L的扫描位置&#xff0c;应该是R&#43;1&#xff0c;比如下面标红的范围&#xff0c;L&#61;3&#xff0c;R&#61;6&#xff0c;当R&#61;7时&#xff0c;顺子中断&#xff0c;则下个顺子从L&#61;4位置开始扫描的话&#xff0c;依旧不能组成顺子&#xff0c;因此我们应该让下个顺子的L直接跳到R&#43;1&#61;8的位置开始扫描。</p> 
<blockquote> 
 <p>int[] count &#61; {0, 0, 0, <span style="color:#fe2c24;">1, 1, 2, 2,</span> 0, 3, 3, 3, 3, 3, 3, 3, 0, 4, 1, 1};</p> 
</blockquote> 
<p>最后&#xff0c;将最长的顺子输出即可。</p> 
<p>需要注意的是&#xff0c;我们可以在上面过程中&#xff0c;实时保存最长顺子&#xff0c;当遇到同长度的顺子时&#xff0c;必然是后面的顺子更优。</p> 
<p></p> 
<h4>JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const my &#61; lines[0].split(&#34;-&#34;);
    const used &#61; lines[1].split(&#34;-&#34;);
    console.log(getResult(my, used));

    lines.length &#61; 0;
  }
});

function getResult(my, used) {
  // 牌面值 映射为 count列表索引值
  const mapToV &#61; new Map([
    [&#34;3&#34;, 3],
    [&#34;4&#34;, 4],
    [&#34;5&#34;, 5],
    [&#34;6&#34;, 6],
    [&#34;7&#34;, 7],
    [&#34;8&#34;, 8],
    [&#34;9&#34;, 9],
    [&#34;10&#34;, 10],
    [&#34;J&#34;, 11],
    [&#34;Q&#34;, 12],
    [&#34;K&#34;, 13],
    [&#34;A&#34;, 14],
    [&#34;2&#34;, 16],
    [&#34;B&#34;, 17],
    [&#34;C&#34;, 18],
  ]);

  /* count每个索引值对应一个牌面值&#xff0c;count元素值就是对应牌面的数量
     牌面值               3  4  5  6  7  8  9  10 J  Q  K  A     2  B  C
     索引值               3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 */
  const count &#61; [0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 1];

  // count列表索引值 隐射为 牌面值
  const mapToK &#61; new Map([
    [3, &#34;3&#34;],
    [4, &#34;4&#34;],
    [5, &#34;5&#34;],
    [6, &#34;6&#34;],
    [7, &#34;7&#34;],
    [8, &#34;8&#34;],
    [9, &#34;9&#34;],
    [10, &#34;10&#34;],
    [11, &#34;J&#34;],
    [12, &#34;Q&#34;],
    [13, &#34;K&#34;],
    [14, &#34;A&#34;],
    [16, &#34;2&#34;],
    [17, &#34;B&#34;],
    [18, &#34;C&#34;],
  ]);

  // 总牌数 减去 自己手中牌数
  for (let k of my) {
    count[mapToV.get(k)] -&#61; 1;
  }

  // 总牌数 减去 已打出去的牌数
  for (let k of used) {
    count[mapToV.get(k)] -&#61; 1;
  }

  let ans &#61; &#34;NO-CHAIN&#34;;
  let maxLen &#61; 0;

  // l为顺子的左边界&#xff0c;[3,10]&#xff0c;即顺子的左边界值最少是count索引3&#xff0c;最多是count索引10
  let l &#61; 3;
  while (l &lt;&#61; 10) {
    const tmp &#61; [];
    for (let r &#61; l; r &lt; 16; r&#43;&#43;) {
      // 如果对应牌数&gt;&#61;1&#xff0c;则可以组顺子
      if (count[r] &gt;&#61; 1) {
        tmp.push(mapToK.get(r));
      } else {
        // 如果对应牌数 &#61;&#61; 0&#xff0c;则顺子中断
        // 顺子必须大于五张牌&#xff0c;且总是记录最长&#xff0c;遇到长度相同的&#xff0c;记录后面发现的顺子
        if (tmp.length &gt;&#61; 5 &amp;&amp; tmp.length &gt;&#61; maxLen) {
          maxLen &#61; tmp.length;
          ans &#61; tmp.join(&#34;-&#34;);
        }
        // 顺子中断处&#43;1&#xff0c;即为下一次顺子的起始位置
        l &#61; r;
        break;
      }
    }
    l&#43;&#43;;
  }

  return ans;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String[] my &#61; sc.nextLine().split(&#34;-&#34;);
    String[] used &#61; sc.nextLine().split(&#34;-&#34;);

    System.out.println(getResult(my, used));
  }

  public static String getResult(String[] my, String[] used) {
    // 牌面值 映射为 count列表索引值
    HashMap&lt;String, Integer&gt; mapToV &#61; new HashMap&lt;&gt;();
    mapToV.put(&#34;3&#34;, 3);
    mapToV.put(&#34;4&#34;, 4);
    mapToV.put(&#34;5&#34;, 5);
    mapToV.put(&#34;6&#34;, 6);
    mapToV.put(&#34;7&#34;, 7);
    mapToV.put(&#34;8&#34;, 8);
    mapToV.put(&#34;9&#34;, 9);
    mapToV.put(&#34;10&#34;, 10);
    mapToV.put(&#34;J&#34;, 11);
    mapToV.put(&#34;Q&#34;, 12);
    mapToV.put(&#34;K&#34;, 13);
    mapToV.put(&#34;A&#34;, 14);
    mapToV.put(&#34;2&#34;, 16);
    mapToV.put(&#34;B&#34;, 17);
    mapToV.put(&#34;C&#34;, 18);

    // count每个索引值对应一个牌面值&#xff0c;count元素值就是对应牌面的数量
    // 牌面值             3  4  5  6  7  8  9  10 J  Q  K  A     2  B  C
    // 索引值             3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
    int[] count &#61; {0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 1};

    // count列表索引值 隐射为 牌面值
    HashMap&lt;Integer, String&gt; mapToK &#61; new HashMap&lt;&gt;();
    mapToK.put(3, &#34;3&#34;);
    mapToK.put(4, &#34;4&#34;);
    mapToK.put(5, &#34;5&#34;);
    mapToK.put(6, &#34;6&#34;);
    mapToK.put(7, &#34;7&#34;);
    mapToK.put(8, &#34;8&#34;);
    mapToK.put(9, &#34;9&#34;);
    mapToK.put(10, &#34;10&#34;);
    mapToK.put(11, &#34;J&#34;);
    mapToK.put(12, &#34;Q&#34;);
    mapToK.put(13, &#34;K&#34;);
    mapToK.put(14, &#34;A&#34;);
    mapToK.put(16, &#34;2&#34;);
    mapToK.put(17, &#34;B&#34;);
    mapToK.put(18, &#34;C&#34;);

    // 总牌数 减去 自己手中牌数
    for (String k : my) {
      count[mapToV.get(k)] -&#61; 1;
    }

    // 总牌数 减去 已打出去的牌数
    for (String k : used) {
      count[mapToV.get(k)] -&#61; 1;
    }

    String ans &#61; &#34;NO-CHAIN&#34;;
    int maxLen &#61; 0;

    // l为顺子的左边界&#xff0c;[3,10]&#xff0c;即顺子的左边界值最少是count索引3&#xff0c;最多是count索引10
    int l &#61; 3;
    while (l &lt;&#61; 10) {
      ArrayList&lt;String&gt; tmp &#61; new ArrayList&lt;&gt;();
      StringJoiner sj &#61; new StringJoiner(&#34;-&#34;);
      for (int r &#61; l; r &lt; 16; r&#43;&#43;) {
        // 如果对应牌数&gt;&#61;1&#xff0c;则可以组顺子
        if (count[r] &gt;&#61; 1) {
          tmp.add(mapToK.get(r));
          sj.add(mapToK.get(r));
        } else {
          // 如果对应牌数 &#61;&#61; 0&#xff0c;则顺子中断
          // 顺子必须大于五张牌&#xff0c;且总是记录最长&#xff0c;遇到长度相同的&#xff0c;记录后面发现的顺子
          if (tmp.size() &gt;&#61; 5 &amp;&amp; tmp.size() &gt;&#61; maxLen) {
            maxLen &#61; tmp.size();
            ans &#61; sj.toString();
          }
          // 顺子中断处&#43;1&#xff0c;即为下一次顺子的起始位置
          l &#61; r;
          break;
        }
      }
      l&#43;&#43;;
    }

    return ans;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
my &#61; input().split(&#34;-&#34;)
used &#61; input().split(&#34;-&#34;)


# 算法入口
def getResult():
    # 牌面值 映射为 count列表索引值
    mapToV &#61; {
        &#34;3&#34;: 3,
        &#34;4&#34;: 4,
        &#34;5&#34;: 5,
        &#34;6&#34;: 6,
        &#34;7&#34;: 7,
        &#34;8&#34;: 8,
        &#34;9&#34;: 9,
        &#34;10&#34;: 10,
        &#34;J&#34;: 11,
        &#34;Q&#34;: 12,
        &#34;K&#34;: 13,
        &#34;A&#34;: 14,
        &#34;2&#34;: 16,
        &#34;B&#34;: 17,
        &#34;C&#34;: 18
    }

    # count每个索引值对应一个牌面值&#xff0c;count元素值就是对应牌面的数量
    # 牌面值           3  4  5  6  7  8  9  10 J  Q  K  A     2  B  C
    # 索引值           3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
    count &#61; [0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 1]

    # count列表索引值 隐射为 牌面值
    mapToK &#61; {
        3: &#34;3&#34;,
        4: &#34;4&#34;,
        5: &#34;5&#34;,
        6: &#34;6&#34;,
        7: &#34;7&#34;,
        8: &#34;8&#34;,
        9: &#34;9&#34;,
        10: &#34;10&#34;,
        11: &#34;J&#34;,
        12: &#34;Q&#34;,
        13: &#34;K&#34;,
        14: &#34;A&#34;,
        16: &#34;2&#34;,
        17: &#34;B&#34;,
        18: &#34;C&#34;
    }

    # 总牌数 减去 自己手中牌数
    for k in my:
        count[mapToV[k]] -&#61; 1

    # 总牌数 减去 已打出去的牌数
    for k in used:
        count[mapToV[k]] -&#61; 1

    ans &#61; &#34;NO-CHAIN&#34;
    maxLen &#61; 0

    # l为顺子的左边界&#xff0c;[3,10]&#xff0c;即顺子的左边界值最少是count索引3&#xff0c;最多是count索引10
    l &#61; 3
    while l &lt;&#61; 10:
        tmp &#61; []
        for r in range(l, 16):
            # 如果对应牌数&gt;&#61;1&#xff0c;则可以组顺子
            if count[r] &gt;&#61; 1:
                tmp.append(mapToK[r])
            # 如果对应牌数 &#61;&#61; 0&#xff0c;则顺子中断
            else:
                # 顺子必须大于五张牌&#xff0c;且总是记录最长&#xff0c;遇到长度相同的&#xff0c;记录后面发现的顺子
                if len(tmp) &gt;&#61; 5 and len(tmp) &gt;&#61; maxLen:
                    maxLen &#61; len(tmp)
                    ans &#61; &#34;-&#34;.join(tmp)
                # 顺子中断处&#43;1&#xff0c;即为下一次顺子的起始位置
                l &#61; r
                break
        l &#43;&#61; 1

    return ans


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>